package william.tree;

/**
 * @author ZhangShenao
 * @date 2024/3/23
 * @description <a href="https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/">...</a>
 */
public class Leetcode235_二叉搜索树的最近公共祖先 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    /**
     * 采用递归算法
     * 对二叉树进行递归dfs遍历,针对当前节点,可能存在以下几种情况:
     * -当前节点就是p节点或q节点,则当前节点就是最近公共祖先,返回当前节点
     * -当前p和q一个大于当前节点,另一个小于当前节点,则当前节点就是最近公共祖先,返回当前节点
     * -p和q都小于当前节点,则继续递归查找左子树
     * -p和q都大于当前节点,则继续递归查找右子树
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //边界条件校验
        if (root == null || p == null || q == null) {
            return null;
        }

        //递归调用
        if (p.val < root.val && q.val < root.val) {   //p和q都小于当前节点,则继续递归查找左子树
            return lowestCommonAncestor(root.left, p, q);
        }
        if (p.val > root.val && q.val > root.val) {  //p和q都大于当前节点,则继续递归查找右子树
            return lowestCommonAncestor(root.right, p, q);
        }

        //剩余情况: 当前节点就是p节点或q节点,或节点p和q位于当前节点的两侧,此时当前节点就是最近公共祖先
        return root;

    }
}
